import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * Description:直接选择排序和希尔排序
 * User: 86183
 * Date: 2023-04-26
 * Time: 8:17
 */
public class sortDeom4 {
    public static void main(String[] args) {
        int [] a = {78,45,12,45,12,34,56};
//        shellSort(a);
        selectSort(a);
        System.out.println(Arrays.toString(a));;
    }
   /*
    *直接选择排序
    * 时间复杂度:O(n^2);
    * 稳定性:不稳定
    */
    private static void selectSort(int[] a) {
        int l = 0;
        int r = a.length - 1;
        while (l < r){
            int min = l;
            int max = l;
            for (int i = l+1; i <= r ; i++) {
                if(a[i] < a[min]){
                    min = i;
                }
                if(a[i] > a[max]){
                    max = i;
                }
            }
            swap(a,l,min);
            if(max == l){
                max = min;
            }
            swap(a,r,max);
            l++;
            r--;
        }
    }

    private static void swap(int[] a, int l, int i) {
        int tmp = a[i];
        a[i] = a[l];
        a[l] = tmp;
    }

    private static void shellSort(int[] a) {
        int gap = a.length;
        while (gap > 1){
            gap /= 2;
            insertSort(a,gap);
        }
    }
    /*
    *希尔排序
    * 时间复杂度:O(n^1.3)
    * 空间复杂度: O(1)
    * 稳定性: 不稳定
     */
    private static void insertSort(int[] a, int gap) {
        for (int i = gap; i < a.length; i++) {
            int j = i - gap;
            int tmp = a[i];
            for (; j >= 0 ; j-=gap) {
                if(a[j] > tmp){
                    a[j+gap] = a[j];
                }else {
                    break;
                }
            }
            a[j+gap] = tmp;
        }
    }
}
